#
# @lc app=leetcode.cn id=20 lang=python3
#
# [20] 有效的括号
#

# @lc code=start
class Solution:
    def isValid(self, s: str) -> bool:
        # 括号成对出现，输入的字符串必须为偶数
        if len(s) % 2 != 0:
            return False
        
        pairs = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        stack = []
        for item in s:
            if item in pairs:
                if not stack or stack[-1] != pairs[item]:   # 栈为空，或者括号顺序不匹配就返回False
                    return False
                stack.pop()
            else:
                stack.append(item)      # 把有括号放入栈
            
        return not stack                # 判断栈是否为空
        
# @lc code=end

